# 给定一个大小为 n 的整数数组，找出其中所有出现超过 ⌊ n/3 ⌋ 次的元素。
# 进阶：尝试设计时间复杂度为 O(n)、空间复杂度为 O(1)的算法解决此问题。
from typing import List

# 蛮力法
class Solution1:
    def majorityElement(self, nums: List[int]) -> List[int]:
        n = len(nums)
        count_dict = {}
        ans = set()
        for num in nums:
            if num not in count_dict:
                count_dict[num] = 1
            else:
                count_dict[num] += 1
            if count_dict[num] > n / 3:
                ans.add(num)
        return list(ans)